package com.justnow.offer;

/**
 * @author justnow
 * Created on 2020-09-08
 * Description
 *
 * 一个数组，找一个数对，使得两个数对之差最大，并且较大数在较小数之前，要求时间复杂度为O(n)
 * https://blog.csdn.net/abbcbbd/article/details/51464699
 *
 *
 * temp[i]用来存储，从开始到下标为i的元素位置，最大数对之差
 *
 * max[i]用来存储，从开始到下标为i的元素位置，最大值
 *
 * i = 0 时，
 * temp[i] = 0;
 * max[i] = A[i]
 *
 * i!=0 时
 * temp[i] = Math.max(temp[i-1], max[i - 1] - A[i]);
 * max[i] = Math.max(max[i - 1], A[i]);
 */
public class Solution30 {
    public static int find(int[] A) {
        int length = A.length;
        int[] temp = new int[length];
        int[] max = new int[length];
        for (int i = 0; i < length; i++) {
           if (i == 0) {
               temp[i] = 0;
               max[i] = A[i];
           } else {
               temp[i] = Math.max(temp[i-1], max[i - 1] - A[i]);
               max[i] = Math.max(max[i - 1], A[i]);
           }
            System.out.println(temp[i]);
        }

        return temp[length - 1];
    }

    public static void main(String[] args) {
        int[] A = {12, 2, -1, 6, 8, 3, 5, 2, 6};
        int i = find(A);
        System.out.println(i);
    }


}
